package org.example.struct.array;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

/**
 * @author liyishan
 * @date 2024/5/8 10:05
 * @apiNote
 */

public class Test00496NextGreaterElement {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[] res = new int[m];
        for (int i = 0; i < m; i++) {
            int j = 0;
            while (j < n && nums1[i] != nums2[j]) {
                j++;
            }
            int k = j + 1;
            while (k < n && nums1[i] > nums2[k]) {
                k++;
            }
            res[i] = k >= n ? -1 : nums2[k];
        }
        return res;
    }

    public int[] nextGreaterElement1(int[] nums1, int[] nums2) {
        Map<Integer,Integer> map = new HashMap<>();
        Deque<Integer> stack = new ArrayDeque<>();
        for(int i = nums2.length-1;i>=0;i--){
            int num = nums2[i];
            while(!stack.isEmpty() && stack.peek() <= num){
                stack.pop();
            }
            map.put(num,stack.isEmpty()?-1:stack.peek());
            stack.push(num);
        }
        int[] res = new int[nums1.length];
        for(int i = 0;i<nums1.length;i++){
            res[i] = map.get(nums1[i]);
        }
        return res;
    }
}
